PC Active 2009 July/August

home *** CD-ROM | disk | FTP | other *** search

/ PC Active 2009 July/August / PC Active NR.227.iso / Software / Games / windows / Freeciv-2.1.9-win32-gtk2-setup.exe / doc / README.AI < prev next >

Wrap

Text File | 2009-03-25 | 13.5 KB | 341 lines

============== THE FREECIV AI ============== CONTENTS ======== Introduction Contacting the current AI developers Long-term AI development goals Want calculations Amortize Estimation of profit from a military operation Selecting military units Ferry system Diplomacy Difficulty levels Things that needs to be fixed Idea space INTRODUCTION ============ The Freeciv AI is widely recognized as being as good as or better military-wise as the AI of certain other games it is natural to compare it with. It is, however, still too easy for experienced players. The code base used to be in a bad shape but it has gotten a lot better. The reason for this is that the developer (Syela) who in a few months put together a working AI had suddenly disappeared. His bright ideas could only be matched by his inability to name variables and to comment the code. Subsequent AI developers were not brave (or stupid?) enough to start from scratch, taking instead a small bite here and there, trying hard not to break much, to understand Syela's original design and only then to throw it away. Or perfect it. Not all code is residing in ai/, but it is also dissolved in little chunks in the whole server/. Aside that, server/settlers.c is only AI stuff - the problem is, that most of it is used also for the auto-settlers, so we can't separate it from the server. server/gotohand.c is a left-over from the previous path-finding system which is slowly being phased out. CONTACTING THE CURRENT AI DEVELOPERS ==================================== AI development has its own mailing list. Send questions to freeciv-ai@freeciv.org, or go to http://www.freeciv.org/index.php/Community_Forums to read the archives or to join up. LONG-TERM AI DEVELOPMENT GOALS ============================== The long-term goals for Freeciv AI development are -> to create a challenging and fun AI for human players to defeat -> to create an AI that can handle all the rules possibilities that Freeciv can offer WANT CALCULATIONS ================= Build calculations are expressed through a structure called ai_choice. This has a variable called "want", which determines how much the AI wants whatever item is pointed to by choice->type. choice->want is -199 get_a_boat < 0 an error == 0 no want, nothing to do <= 100 normal want > 100 critical want, used to requisition emergency needs > ??? probably an error (1024 is a reasonable upper bound) > 200 Frequently used as a cap. When want exceeds this value, it is reduced to a lower number. These are ideal numbers, your mileage while travelling through the code may vary considerably. Technology and diplomats, in particular, seem to violate these standards. AMORTIZE ======== Hard fact: amortize(benefit, delay) returns benefit * ((MORT - 1)/MORT)^delay (where "^" == "to the power of") Speculation: What is better, to receive 10$ annually starting in 5 years from now or 5$ annually starting from this year? How can you take inflation into account? The function amortize is meant to help you answer these questions. To achieve this, it rescales the future benefit in terms of todays money. Suppose we have a constant rate of inflation, x percent. Then in five years time 10$ will buy as much as 10*(100/(100+x))^5 will buy today. Denoting 100/(100+x) by q we get the general formula, N dollars Y years from now will be worth N*q^Y in todays money. If we will receive N every year starting Y years from now, the total amount receivable (in todays money) is N*q^Y / (1-q) --- this is the sum of infinite geometric series. This is exactly the operation that amortize performs, the multiplication by some q < 1 raised to power Y. Note that the factor 1/(1-q) does not depend on the parameters N and Y and can be ignored. The connection between MORT constant and the inflation rate x is given by (MORT - 1) / MORT = q = 100 / (100 + x). Thus the current value of MORT = 24 corresponds to the inflation rate (or the rate of expansion of your civ) of 4.3% Most likely this explanation is not what the authors of amortize() had in mind, but the basic idea is correct: the value of the payoff decays exponentially with the delay. The version of amortize used in the military code (military_amortize()) remains a complete mystery. ESTIMATION OF PROFIT FROM A MILITARY OPERATION ============================================== This estimation is implemented by kill_desire function (which isn't perfect: multi-victim part is flawed) plus some corrections. In general, Want = Operation_Profit * Amortization_Factor where * Amortization_Factor is completely beyond me (but it's a function of the estimated time length of the operation). * Operation_Profit = Battle_Profit - Maintenance where * Maintenance = (Support + Unhappiness_Compensation) * Operation_Time (here unhappiness is from military unit being away from home and Support is the number of shields spent on supporting this unit per turn ) * Battle_Profit = Shields_Lost_By_Enemy * Probability_To_Win - Shields_Lost_By_Us * Probability_To_Lose That is Battle_Profit is a probabilistic average. It answer the question "how much better off, on average, we would be from attacking this enemy unit?" SELECTING MILITARY UNITS ======================== The code dealing with choosing military units to be built and targets for them is especially messy. Here is what we've managed to decipher. Military units are requested in military_advisor_choose_build function. It first considers the defensive units and then ventures into selection of attackers (if home is safe). There are 2 possibilities here: we just build a new attacker or we already have an attacker which was forced, for some reason, to defend. In the second case it's easy: we calculate how good the existing attacker is and if it's good, we build a defender to free it up. Building a brand-new attacker is more complicated. Firstly, ai_choose_attacker_* functions are charged to find the first approximation to the best attacker that can be built here. This prototype attacker is selected using very simple attack_power * speed formula. Then (already in kill_something_with) we search for targets for the prototype attacker (using find_something_to_kill). Having found a target, we do the last refinement by calling process_attacker_want to look for the best attacker type to take out the target. This type will be our attacker choice. Note that the function process_attacker_want has side-effects wrt the tech selection. Here is an example: First ai_choose_attacker_land selects a Dragoon because it's strong and fast. Then find_something_to_kill finds a victim for the (virtual) Dragoon, an enemy Riflemen standing right next to the town. Then process_attacker_want figures out that since the enemy is right beside us, it can be taken out easier using an Artillery. It also figures that a Howitzer would do this job even better, so bumps up our desire for Robotics. This is the idea, anyway. In practice, it is more complicated and probably less efficient. FERRY SYSTEM ============ The ferry (i.e. boats transporting land units) system of Freeciv is probably better described by statistical mechanics than by logic. Both ferries and prospective passenger (PP) move around in what looks like a random fashion, trying to get closer to each other. On average, they succeed. This behaviour has good reasons behind it, is hell to debug but means that small bugs don't affect overall picture visibly (and stay unfixed as a result). Each turn both boats and PPs forget all about prior arrangements (unless the passenger is actually _in_ the boat). Then each will look for the closest partner, exchange cards and head towards it. This is done in a loop which goes through all units in essentially random order. Because most units recalculate their destination every turn, ignoring prior arrangements is the only good strategy -- it means that a boat will not rely on the PP to notify it when it's not needed anymore. This is not very effective but can only be changed when the PPs behave more responsibly. See diplomat code for more responsible behaviour -- they try to check if the old target is still good before trying to find a new one. When a boat has a passenger, it's a different story. The boat doesn't do any calculations, instead one of the passengers is given full control and it is the passenger who drives the boat. Here are the main data fields used by the system. Value of ai.ferry in the passenger unit is: FERRY_NONE : means that the unit has no need of a ferry FERRY_WANTED : means that the unit wants a ferry >0 : id of it's ferry Value of ai.passenger in the ferry unit can be either of: FERRY_AVAILABLE : means that the unit is a ferry and is available >0 : id of it's passenger When boat-building code stabilizes, it can be seen how many free boats there are, on average, per PP. If there are more boats than PPs, it makes sense that only PPs should look for boats. If boats are few, they should be the ones choosing. This can be done both dynamically (both possibilities are coded and the appropriate is chosen every turn) and statically (after much testing only one system remains). Now they exist in parallel, although developed to a different degree. DIPLOMACY ========= The AI's diplomatic behaviour is current only regulated by the 'diplomacy' server setting. In default rules, the AI starts out in NO_CONTACT mode, and proceeds to NEUTRAL on first-contact. AI is not very trusting for NEUTRAL and PEACE modes, but once it hits ALLIANCE, this changes completely, and it will happily hand over any tech and maps it has to you. The only thing that will make the AI attack you then is if you build a spaceship. For people who want to hack at this part of the AI code, please note * pplayers_at_war(p1,p2) returns FALSE if p1==p2 * pplayers_non_attack(p1,p2) returns FALSE if p1==p2 * pplayers_allied(p1,p2) returns TRUE if p1==p2 * pplayer_has_embassy(p1,p2) returns TRUE if p1==p2 i.e. we do not ever consider a player to be at war with himself, we never consider a player to have any kind of non-attack treaty with himself, and we always consider a player to have an alliance with himself. The introduction of diplomacy is fraught with many problems. One is that it usually gains only human players, not AI players, since humans are so much smarter and know how to exploit diplomacy, while for AIs they mostly only add constraints on what it can do. Another is that it can be very difficult to write diplomacy that is useful for and not in the way of modpacks. Which means diplomacy either has to be optional, or have fine-grained controls on who can do what diplomatic deals to whom, set from rulesets. The latter is not yet well implemented. DIFFICULTY LEVELS ================= There are currently five difficulty levels: 'novice', 'easy', 'medium', 'hard' and 'experimental'. The 'hard' level is no-holds-barred, while 'medium' has a number of handicaps. In 'easy', the AI also does random stupid things through the ai_fuzzy function. The 'experimental' level is only for coding - you can gate new code with the H_EXPERIMENTAL handicap and test 'experimental' level AIs against 'hard' level AIs. In 'novice' the AI researches slower than normal players. Other handicaps used are: H_RATES, can't set its rates beyond government limits H_TARGETS, can't target anything it doesn't know exists H_HUTS, doesn't know which unseen tiles have huts on them H_FOG, can't see through fog of war The other defined handicaps (in common/player.h) are not currently in use. THINGS THAT NEED TO BE FIXED ============================ * Cities don't realize units are on their way to defend it. * AI doesn't understand that some wonders are obsolete, that some wonders become obsolete, and doesn't upgrade units. * AI doesn't understand how to favor trade when it needs luxury. * AI builds cities without regard to danger at that location. * AI won't build cross-country roads outside of city radii. [Note: There is patch that permits the AI to build cross country roads/rail. Unfortunately, it makes it too easy for the AI to be invaded. Addendum: Can someone actually test this? Defeating an AI that uses roads is more fun, but is it really that much easier?] * Locally_zero_minimap is not implemented when wilderness tiles change. * If no path to chosen victim is found, new victim should be chosen. * AI doesn't know how to make trade routes or when. It should try to build trade routes for its best cities (most building bonuses and least corruption) by moving caravans there and changing homecity. * Emergencies in two cities at once aren't handled properly. * Explorers will not use ferryboats to get to new lands to explore. * AI sometimes believes that wasting a horde of weak military units to kill one enemy is profitable (PR#1340) * Stop building ships and shore defense in landlocked cities with a pond adjacent. * Make the AI building evaluation code use the new buildings.ruleset. * Fix the AI valuation of supermarket. (It currently never builds it). See farmland_food() and ai_eval_buildings() in advdomestic.c * Teach the AI to coordinate the units in an attack (ok, this one is a bit big...) IDEA SPACE ========== * Friendly cities can be used as beachheads * Assess_danger should acknowledge positive feedback between multiple attackers * It would be nice for bodyguard and charge to meet en-route more elegantly. * struct choice should have a priority indicator in it. This will reduce the number of "special" want values and remove the necessity to have want capped, thus reducing confusion.